package com.clstu.sort;

import java.util.Arrays;

/**
 * 演示插入排序的过程 ---(优化后似乎没有提升)---效果上明显快于选择排序和冒泡排序!!!!!
 */
public class InsertSort {
    public static void main(String[] args) {
        //测试插入排序
        //创建数组
//        int[] arr = {6,5,4,3,2,1,0};
//        insertSort(arr);
        //测试速度
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*80000);
        }
        long start = System.currentTimeMillis();
        insertSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("插入排序80000个数据耗时:"+(end-start)+"ms");//577ms,时间复杂度O(n*n),但明显快于选择法排序和冒泡法排序
        start = System.currentTimeMillis();
        insertSort(arr);
        end = System.currentTimeMillis();
        System.out.println("插入排序80000个数据(有序的)耗时:"+(end-start)+"ms");//0ms,
    }

    //编写方法实现插入排序
    public static void insertSort(int[] arr){
        //思路分析:
        //插入排序过程:
        //1.先将前面i(从1开始)个数据看成有序表,将第i+1个数据插入
        //2.先用insertVal保存i+1个数据的值,insertIndex设置为i依次向前找,
        // 如果没找到,就将insertIndex的数据向后移,如果找到,arr[insertIndex] = insertVal
        // 如果找到最前面都没有找到位置,直接插在第一个
        int insertVal ;
        int insertIndex;
        for (int i = 1; i < arr.length; i++) {
            //从第i个开始向前找
            insertIndex = i-1;
            insertVal = arr[i];
            //没找到位置就将找过的数都后移一个位置
            while (insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            //循环结束有一定是找到了,就插入到该index的后面就可以了,所以需要+1
            if(insertIndex+1 != i) {
                arr[insertIndex + 1] = insertVal;
            }
            //看看结果
//            System.out.println("插入排序第"+i+"次排序后:"+ Arrays.toString(arr));
        }
    }
}
